package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by 朱城委 on 2021/8/30.<br><br>
 *
 * 中等：子集Ⅱ
 */
public class Topic90 {

    public static void main(String[] args) {
        Topic90 instance = new Topic90();

        int[] array = new int[] {1,2,2};
        System.out.println(instance.subsetsWithDup(array));

        array = new int[] {0};
        System.out.println(instance.subsetsWithDup(array));
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);
        for(int i = 0; i <= nums.length; i++) {
            helper(nums, new ArrayList<>(), result, i, 0);
        }

        return result;
    }

    private void helper(int[] nums, List<Integer> list, List<List<Integer>> result, int size, int start) {
        if(list.size() == size) {
            result.add(new ArrayList<>(list));
            return ;
        }

        for(int i = start; i < nums.length; i++) {
            if(i != start && nums[i] == nums[i - 1]) {
                continue;
            }

            list.add(nums[i]);
            helper(nums, list, result, size, i + 1);
            list.remove(list.size() - 1);
        }
    }
}
